
#include "lex_tree.h"

#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "common/alloc.h"


/*
 *
 * Data Structures
 *
 */

struct Entry
{
    FileChar        character;
    struct Node *   node;

    // NB: this is to optimize saving process
    FileOffset node_offset;
};

struct EntriesArray
{
    int count;
    int allocated;
    struct Entry * arr;
};

struct Node
{
    struct Node * parent;

    struct EntriesArray entries;

    // NB: this is to optimize saving process
    FileOffset parent_node_offset;
};


/*
 *
 * Algorithms
 *
 */

struct Node * new_node(struct Node * parent)
{
    struct Node * node = xmalloc(sizeof(struct Node));
    memset(node, 0, sizeof(struct Node));
    node->parent = parent;
    return node;
}

#define BSEARCH_NS(name)        fchar_entry_##name
#define BSEARCH_ARRAY_TYPE      struct Entry *
#define BSEARCH_KEY_TYPE        FileChar
#define BSEARCH_3W_COMPARE(array, index, key) (key - array[index].character)
#include <templates/bsearch.h>


#define ENTRIES_ARR_GROW_SIZE (16)

struct Node * add_lexeme(const FileChar * lexeme, const FileChar * lexeme_end, struct Node * node)
{
    for (; lexeme < lexeme_end; ++lexeme)
    {
        FileChar ch = *lexeme;
        struct EntriesArray * e = &node->entries;
        int index = fchar_entry_binary_search(e->arr, e->count, ch);

        if (index < 0)
        {
            // insert new node at the index
            index = ~index;
            if (e->count == e->allocated)
            {
                // resize entries array
                e->allocated += ENTRIES_ARR_GROW_SIZE;
                e->arr = xrealloc(e->arr, e->allocated * sizeof(struct Entry));
            }
            memmove(e->arr + index + 1, e->arr + index, (e->count - index) * sizeof(struct Entry));
            ++e->count;

            struct Entry * new_entry = e->arr + index;
            new_entry->character = ch;
            new_entry->node = new_node(node);
        }

        struct Entry * entry = e->arr + index;
        node = entry->node;
    }

    return node;
}

void free_node(struct Node * node)
{
    int i;
    struct EntriesArray * e = &node->entries;

    for (i = 0; i < e->count; ++i)
    {
        free_node(e->arr[i].node);
    }

    xfree(e->arr);
    xfree(node);
}


// serializing code

static void ens_fwrite(FILE * fdest, const void * buf, size_t size)
{
    size_t written = fwrite(buf, 1, size, fdest);
    if (written != size)
    {
        fprintf(stderr, "I/O error: can't write more bytes to the destination file\n");
        abort();
    }
}


// TODO: merge fdest + offset_delta to the single member
static void save_rec_node(struct Node * node, FILE * fdest)
{
    int i;

    // write each child node
    for (i = 0; i < node->entries.count; ++i)
    {
        struct Entry * entry = node->entries.arr + i;
        save_rec_node(entry->node, fdest);
    }

    // write file node
    struct FileNode file_node;
    file_node.parent_node_offset = node->parent_node_offset;
    file_node.entry_count = node->entries.count;
    ens_fwrite(fdest, &file_node, sizeof(struct FileNode));

    // write each entry
    for (i = 0; i < node->entries.count; ++i)
    {
        struct Entry * entry = node->entries.arr + i;

        struct FileEntry file_entry;
        file_entry.character = entry->character;
        file_entry.node_offset = entry->node_offset;

        ens_fwrite(fdest, &file_entry, sizeof(struct FileEntry));
    }
}


FileOffset recalc_offsets_recursive(struct Node * node, FileOffset cur_offset, int parent_entry_index)
{
    int i;

    // render childs
    for (i = 0; i < node->entries.count; ++i)
    {
        struct Entry * entry = node->entries.arr + i;
        cur_offset = recalc_offsets_recursive(entry->node, cur_offset, i);
    }

    // this node will be recorded at the cur_offset, so update all it's childs
    for (i = 0; i < node->entries.count; ++i)
    {
        struct Entry * entry = node->entries.arr + i;
        entry->node->parent_node_offset = cur_offset;
    }

    // save current node's offset to the parent entries array
    assert(node->parent != NULL);
    node->parent->entries.arr[parent_entry_index].node_offset = cur_offset;

    // update cur offset - initial + node + all the node's entries
    cur_offset = cur_offset + sizeof(struct FileNode) + node->entries.count * sizeof(struct FileEntry);

    return cur_offset;
}

void recalc_offsets(struct Node * node, struct FileHeader * header)
{
    // introduce fake entry to safely calculate node's offset
    struct Entry fake_entry;
    struct Node fake_parent;
    fake_parent.entries.arr = &fake_entry;
    fake_parent.entries.count = 1;

    assert(node->parent == NULL);
    node->parent = &fake_parent;

    header->tree_block_size = recalc_offsets_recursive(node, 0, 0);
    node->parent_node_offset = 0;

    // restore root's node parent
    node->parent = NULL;

    // return root node's offset
    header->root_node_offset = fake_entry.node_offset;
}

bool save_tree_to_file(struct Node * node, FILE * fdest)
{
    bool result = true;

    // args check
    if (fdest == NULL || node == NULL)
    {
        result = false;
    }

    if (result)
    {
        struct FileHeader file_header;
        recalc_offsets(node, &file_header);

        ens_fwrite(fdest, &file_header, sizeof(struct FileHeader));
        save_rec_node(node, fdest);
    }

    return result;
}
